/**
 * @author LKQ
 * @date 2021/11/19 22:02
 * @description
 * 给定一个正整数n ，你可以做如下操作：
 * 如果n是偶数，则用n / 2替换n 。
 * 如果n是奇数，则可以用n + 1或n - 1替换n 。
 * n变为 1 所需的最小替换次数是多少？
 *
 * 1 <= n <= 231 - 1
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/integer-replacement
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class IntegerSubstitution {
    public static void main(String[] args) {
        System.out.println(integerReplacement(2147483647));
    }
    public static int integerReplacement(int n) {
        return (int)replace((long)n);
    }

    public static long replace(long n) {
        if (n==1) {
            return 0;
        }
        if (n % 2 == 0) {
            return 1 + replace( n / 2);
        }else {
            return 1 + Math.min(replace( n+1) , replace(n-1));
        }
    }
}
